import java.util.Arrays;
import java.util.Collections;
import java.util.Objects;

public class Main {
    /**
     * 卖买股票的最佳时机1
     */
//    class Solution {
//        public int maxProfit(int[] prices) {
//            int n = prices.length;
//            int ret = 0;
//            int preMin = Integer.MAX_VALUE;
//            for(int i = 0; i <n; i++) {
//                ret = Math.max(ret, prices[i] - preMin);
//                preMin = Math.min(preMin, prices[i]);
//            }
//            return ret;
//        }

    /**
     * 买卖股票的最佳时机2
     */
   /* class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int ret = 0;
            for(int i = 0; i < n; i++) {
                int j = i;
                while(j + 1 < n && prices[j + 1] > prices[j]) j++;
                ret += prices[j] - prices[i];
                i = j;
            }
            return ret;
        }
    }
    */
    /*class Solution {
        public int maxProfit(int[] prices) {

            //将每天的收益加起来
            //每一小段中 只要是能赚钱的 那么就给他加起来
            int ret = 0;
            for(int i = 1; i < prices.length; i++) {
                //
                if(prices[i] > prices[i - 1]) {
                    ret += prices[i] - prices[i - 1];
                }
            }
            return ret;
        }
    }*/



    /**
     *k次取反后最大化的数组和
     *
     */
   /* class Solution {
        public int largestSumAfterKNegations(int[] nums, int k) {
            int n = nums.length;
            int m = 0;//记录负数个数
            int minElement = Integer.MAX_VALUE;//用来记录所有数成正数后 数组的最小值
            for(int x : nums) {
                if(x < 0) {
                    m++;
                }
                minElement = Math.min(minElement, Math.abs(x));
            }
            int ret = 0;
            if(m > k) {
                Arrays.sort(nums);
                for(int i = 0; i < k; i++) {
                    ret += -nums[i];
                }
                for(int i = k; i < n; i++) {
                    ret += nums[i];
                }
            }else{
                for(int x : nums) {
                    ret += Math.abs(x);
                }
                if((k - m) % 2 != 0) {
                    //是奇数
                    ret -= 2 * minElement;
                }
            }
            return ret;
        }
    }*/

    /**
     * 按身高排序
     */
    /*class Solution {
        public String[] sortPeople(String[] names, int[] heights) {
            //对下标排序--非常常用的解决排序中不想对原始数组的相对顺序进行修改
            int n = names.length;
            Integer[] index = new Integer[n];
            for(int i = 0; i < n; i++) {
                index[i] = i;
            }
            Arrays.sort(index, (a ,b) -> {
                return heights[b] - heights[a];
            });
            Collections.so
            String[] ret = new String[n];
            for(int i = 0; i < n; i++) {
                ret[i] = names[index[i]];
            }
            return ret;
        }
    }*/

    /**
     * 优势洗牌[--田忌赛马
     */
//    class Solution {
//        public int[] advantageCount(int[] nums1, int[] nums2) {
//            int n = nums1.length;
//            int left = 0;
//            int right = n - 1;
//            Integer[] index2 = new Integer[n];
//            int[] ret = new int[n];
//            for(int i = 0; i < n; i++) {
//                index2[i] =  i;
//            }
//            Arrays.sort(nums1);
//            //排序下标数组
//            Arrays.sort(index2, (a,b)->{
//                return nums2[a] - nums2[b];
//            });
//            for(int i = 0; i < n; i++) {
//                if(nums1[i] > nums2[index2[left]]) {
//                    ret[index2[left++]] = nums1[i];
//                }else{
//                    ret[index2[right--]] = nums1[i];
//                }
//            }
//            return ret;
//        }
//    }

    /**
     *最长回文串
     */
//    class Solution {
//        public int longestPalindrome(String s) {
//            char[] ch = s.toCharArray();
//            int n = s.length();
//            int ret = 0;
//            //统计每个字符出现的次数
//            int[] count = new int[60];
//            for(int i = 0; i < n; i++) {
//                count[ch[i] - 'A']++;
//            }
//            for(int x : count) {
//                ret += x / 2 * 2;
//            }
//
//            return ret == n ? ret : ret + 1;
//        }
//    }

    /**
     * 增减字符串匹配
     */
//    class Solution {
//        public int[] diStringMatch(String s) {
//            int n = s.length();
//            int[] ret = new int[n + 1];
//            char[] ch = s.toCharArray();
//            int min = 0;
//            int max = n;
//            for(int i  = 0; i < n; i++) {
//                if(ch[i] == 'I') {
//                    ret[i] = min++;
//                } else {
//                    ret[i] = max--;
//                }
//            }
//            ret[n] = min;
//            return ret;
//        }
//    }

    /**
     *
     * 分配饼干
     */
//    class Solution {
//        public int findContentChildren(int[] g, int[] s) {
//            Arrays.sort(g);
//            Arrays.sort(s);
//            int m = g.length;
//            int n = s.length;
//            int ret = 0;
//            for(int i =0,j=0; i < m  && j < n; i++,j++) {
//                while(j < n &&s[j] < g[i]) j++;
//                if(j < n) ret++;
//            }
//            return ret;
//        }
//    }

    /**
     *
     *
     *最优除法
     */
//    class Solution {
//        public String optimalDivision(int[] nums) {
//            int n = nums.length;
//            String ret = "";
//            if(n == 1) return ret + nums[0];
//            if(n == 2) {
//                ret = ret + nums[0] + "/" + nums[1];
//                return ret;
//            }
//            //第一个数 一定做分子 第二个数一定做分母 然后在第二个数前面加 (
//            //所以我们可以先将前部分先写好
//            ret += nums[0] + "/(" + nums[1];
//            for(int i = 2; i < n; i++) {
//                ret += "/" + nums[i];
//            }
//            return ret + ")";
//        }
//    }

    /**
     * 跳跃游戏2 动态规划版本
     */
//    class Solution {
//        public int jump(int[] nums) {
//            int n = nums.length;
//            if(n == 1) return 0;
//            if(n == 2) return 1;
//            int[] dp = new int[n]; //表示从0开始 到 i 位置的最小跳跃次数
//            Arrays.fill(dp, Integer.MAX_VALUE);
//            dp[0] = 0;
//            dp[1] = 1;
//            for(int i = 2; i < n; i++) {
//                for(int j = 0; j < i; j++) {
//                    if((j + nums[j]) >= i) {
//                        dp[i] = Math.min(dp[i], dp[j] + 1);
//                    }
//                }
//            }
//            return dp[n - 1];
//        }
//    }

    /**
     * 贪心
     */
//    class Solution {
//        public int jump(int[] nums) {
//            int n = nums.length;
//            //贪心策略: 不断的去贪 下一次起跳区间的最右边
//            int left = 0, right = 0, maxPos = 0, ret = 0;
//            while (left <= right) {
//                if (maxPos >= n - 1) return ret;
//                for (int i = left; i <= right; i++) {
//                    maxPos = Math.max(maxPos, i + nums[i]);
//                }
//                left = right + 1;
//                right = maxPos;
//                ret++;
//            }
//            return -1;
//        }
//    }

    /**
     * 跳跃游戏
     */
//    class Solution {
//        public boolean canJump(int[] nums) {
//            int n = nums.length;
//            int ret = 0, left = 0, right = 0, maxPos = 0;
//            while(left <= right) {
//                if(maxPos >= n - 1) {
//                    //已经到达最后一个位置了
//                    return true;
//                }
//                for(int i = left; i <= right; i++) {
//                    maxPos = Math.max(maxPos, nums[i] + i);
//                }
//                left = right + 1;
//                right = maxPos;
//            }
//            return false;
//        }
//    }

    /**
     * 加油站
     */
//        class Solution {
//            public int canCompleteCircuit(int[] gas, int[] cost) {
//                int n = gas.length;
//                for(int i = 0; i < n; i++) {
//                    int rest = 0;
//                    int step = 0;
//                    for(; step < n; step++) {
//                        int index = (i + step) % n;
//                        rest = rest + gas[index] - cost[index];
//                        if(rest < 0) {
//                            break;
//                        }
//                    }
//                    if(rest >= 0) {
//                        return i;
//                    }
//                    i = i + step;
//                }
//                return -1;
//            }
//        }





}
